package 代码随想2._1数组;

/**
 * @author XXX
 * @date 2024-01-13 16:40
 */

/**
 *https://leetcode.cn/problems/remove-element/description/
 * 双指针
 */
public class _2移除元素 {
    public int removeElement(int[] nums, int val) {
        int slow = 0 , fast = 0;
        for(;fast<nums.length;fast++){
            if(nums[fast]!=val)
                nums[slow++] = nums[fast];
        }
        return slow;
    }

    public int removeElement2(int[] nums, int val) {
        int left = 0 , right = nums.length -1;
        while (left<=right){
            while (left<=right && nums[left]!=val)
                ++left;
            while (right>=left && nums[right]==val)
                right--;
            if(left<right)
                nums[left++] = nums[right--];
        }
        return left;
    }
}

/**
 * https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
 */
class 删除有序数组中的重复项{
    public int removeDuplicates(int[] nums) {
        int slow = 0 , fast = 1;
        for(;fast<nums.length;fast++){
            if(nums[fast]!=nums[slow]){
                nums[++slow] = nums[fast];
            }
        }
        return slow+1;
    }
}

/**
 * https://leetcode.cn/problems/move-zeroes/description/
 */
class 移动零{
    public void moveZeroes(int[] nums) {
        int slow = 0 , fast = 0;
        for(;fast<nums.length;fast++){
            if(nums[fast]!=0){
                nums[slow++] = nums[fast];
            }
        }
        for(int i=slow;i<nums.length;i++)
            nums[i] = 0;
    }
}

/**
 * https://leetcode.cn/problems/backspace-string-compare/description/
 */
class 比较含退格的字符串{
    public boolean backspaceCompare(String s, String t) {
        char[] a = s.toCharArray();
        char[] b = t.toCharArray();
        int slowa = 0 , fasta = 0;
        int slowb = 0 , fastb = 0;
        for(;fasta<a.length;fasta++){
            if(a[fasta]!='#')
                a[slowa++] = a[fasta];
            else
                if (slowa>0)
                    slowa--;
        }
        for(;fastb<b.length;fastb++){
            if(b[fastb]!='#' )
                b[slowb++] = b[fastb];
            else
                if(slowb>0)
                    slowb--;
        }
        return new String(a).substring(0,slowa).equals(new String(b).substring(0,slowb));
    }


    public boolean backspaceCompare2(String s, String t) {
        int i = s.length() - 1 , j = t.length() - 1;
        int skipS = 0 , skipT = 0;
        while (i>=0 || j >=0){
            while (i>=0){
                if(s.charAt(i)=='#'){
                    skipS++;
                    i--;
                }else if(skipS>0){
                    skipS--;
                    i--;
                }else {
                    break;
                }
            }

            while (j>=0){
                if(t.charAt(j)=='#'){
                    skipT++;
                    j--;
                }else if(skipT>0){
                    skipT--;
                    j--;
                }else {
                    break;
                }
            }

            if(i>= 0 && j>= 0){
                if(s.charAt(i)!=t.charAt(j))
                    return false;
            }else{
                if(i>=0 || j>=0)
                    return false;
            }
            i--;
            j--;
        }
        return true;
    }
}

/**
 * https://leetcode.cn/problems/squares-of-a-sorted-array/description/
 */
class 有序数组的平方{
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        for (int i = 0, j = n - 1, pos = n - 1; i <= j;) {
            if (nums[i] * nums[i] > nums[j] * nums[j]) {
                ans[pos] = nums[i] * nums[i];
                ++i;
            } else {
                ans[pos] = nums[j] * nums[j];
                --j;
            }
            pos--;
        }
        return ans;
    }
}
